iT邦幫忙

2025 iThome 鐵人賽

DAY 21
0
自我挑戰組

從零開始學習LeetCode系列 第 21

Day 21 Missing Number

  • 分享至 

  • xImage
  •  

題目:給定一個包含 n 個不同整數的陣列 nums,每個整數都在範圍 [0, n] 之間。
請找出陣列中缺少的那個數字
https://ithelp.ithome.com.tw/upload/images/20251005/20169339PkWw9glgWi.jpg


解法一
https://ithelp.ithome.com.tw/upload/images/20251005/20169339wU6ViGj9Sb.jpg

  • 直觀但慢
  • 依序檢查 0 ~ n 的每個數字,看它是否存在於陣列中。
    沒出現的那個,就是缺少的數

註解

  • len(nums):陣列長度 n
  • 用 range(n + 1) 代表所有可能的數字(包含 n)
  • 用 in 檢查是否存在陣列中
  • 時間複雜度 O(n²),因為 in 每次都要掃整個陣列

理解

  • 想像你有一份 0~n 的點名表,一個一個名字叫:
    「0 在嗎?1 在嗎?…」
    結果發現有人沒來,那個人就是缺少的數。

解法二
https://ithelp.ithome.com.tw/upload/images/20251005/20169339T75S6shcFI.jpg

  • 查找速度快
  • Hash Set(集合法)
  • 把陣列轉成 set(集合),再檢查 0~n 哪個不在集合裡

註解

  • set(nums):轉成集合,查找效率 O(1)
  • 依序檢查每個數是否存在於集合中
  • 時間 O(n),空間 O(n)

理解

  • 這就像你用「快速查名冊」代替一張一張點名
    集合幫你快速知道誰有來誰沒來,速度快多了

解法三
https://ithelp.ithome.com.tw/upload/images/20251005/20169339keB6XpvR7Y.jpg

  • 數學法(Sum Formula)
  • 利用數學公式:
    前 n 個自然數總和是 n * (n + 1) / 2
    缺少的數 = 理論總和 − 實際總和

註解

  • n * (n + 1) // 2:期望的總和(完整序列)
  • sum(nums):實際陣列的總和
  • 兩者相減就得到缺少的數字
  • 時間 O(n),空間 O(1)

理解

  • 這就像你有一份完整的「總分清單」,但有一項缺了,
    用總分減掉現有的分數總和,就知道誰沒交作業

上一篇
Day 20 Majority Element
下一篇
Day 22 Remove Element
系列文
從零開始學習LeetCode24
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言